package sword_to_1;

public class LeeCode_12 {
    public static void main(String[] args) {
        System.out.println(exist(new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'E', 'S'},
                {'A', 'D', 'E', 'E'}
        }, "ABCESEEEFS"));
    }
    private static boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)){
                    if (dfs(i, j, new boolean[m][n], word, 0, board)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private static boolean dfs(int i, int j, boolean[][] used, String word, int index, char[][] board){
        if (index >= word.length()){
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length){
            return false;
        }
        if (used[i][j]){
            return false;
        }
        char goal = word.charAt(index);
        if (board[i][j] == goal){
            used[i][j] = true;
        }else {
            return false;
        }
        boolean f1 = dfs(i + 1, j, used, word, index + 1, board);
        boolean f2 = dfs(i - 1, j, used, word, index + 1, board);
        boolean f3 = dfs(i, j + 1, used, word, index + 1, board);
        boolean f4 = dfs(i, j - 1, used, word, index + 1, board);
        if (!(f1 || f2 || f3 || f4)){
            used[i][j] = false;
            return false;
        }else {
            return true;
        }
    }
}
